package LCR_code;

import javafx.util.Pair;

import java.util.HashSet;

/**
 * @author blh
 * @date 2024年09月09日 15:07
 */
public class LCR_129_99 {
    HashSet<Pair<Integer, Integer>> seen = new HashSet<>();
    boolean res = false;
    int m, n;


    public static void main(String[] args) {
        LCR_129_99 method = new LCR_129_99();
        boolean abcced = method.wordPuzzle(new char[][]{{'a', 'b'}}, "ba");
        System.out.println(abcced);
    }

    public boolean wordPuzzle(char[][] grid, String target) {
        m = grid.length;
        n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == target.charAt(0)) {
                    seen.clear();
                    seen.add(new Pair<>(i, j));
                    dfs(1, i, j, grid, target, seen);
                }
            }
        }
        return res;
    }

    private void dfs(int index, int i, int j, char[][] grid, String target, HashSet<Pair<Integer, Integer>> seen) {

        if (index == target.length()) {
            res = true;
            return;
        }

        // 从上下左右四个方向获得下一个
        // 上
        if (i - 1 >= 0 && !seen.contains(new Pair<>(i - 1, j)) && grid[i - 1][j] == target.charAt(index)) {
            seen.add(new Pair<>(i - 1, j));
            index++;
            dfs(index, i - 1, j, grid, target, new HashSet<>(seen));
            index--;
            seen.remove(new Pair<>(i - 1, j));
        }

        // 下
        if (i + 1 < m && !seen.contains(new Pair<>(i + 1, j)) && grid[i + 1][j] == target.charAt(index)) {
            seen.add(new Pair<>(i + 1, j));
            index++;
            dfs(index, i + 1, j, grid, target, new HashSet<>(seen));
            index--;
            seen.remove(new Pair<>(i + 1, j));
        }

        // 左
        if (j - 1 >= 0 && !seen.contains(new Pair<>(i, j - 1)) && grid[i][j - 1] == target.charAt(index)) {
            seen.add(new Pair<>(i, j - 1));
            index++;
            dfs(index, i, j - 1, grid, target, new HashSet<>(seen));
            index--;
            seen.remove(new Pair<>(i, j - 1));
        }

        // 右
        if (j + 1 < n && !seen.contains(new Pair<>(i, j + 1)) && grid[i][j + 1] == target.charAt(index)) {
            seen.add(new Pair<>(i, j + 1));
            index++;
            dfs(index, i, j + 1, grid, target, new HashSet<>(seen));
            seen.remove(new Pair<>(i, j + 1));
        }
    }
}
